package com.zlk.algorithm.algorithm.sort.merge;

import org.junit.Test;

// 翻转对数量
//给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
//你需要返回给定数组中的重要翻转对的数量。
// 测试链接 : https://leetcode.cn/problems/reverse-pairs/
public class Code02_ReversePairs {


	@Test
	public void test(){
		//[2147483647,2147483647,2147483647,2147483647,2147483647,2147483647]
		System.out.println(reversePairs(new int[]{2147483647,2147483647,2147483647,2147483647,2147483647,2147483647}));
	}
	// 整体思路利用归并的分治思想，左边计算的数+右边计算的数+ merge的数
	// 排序加速求解，（为啥排序不影响count，数据已经统计了，后续变动位置也不影响）
	public int reversePairs(int[] nums) {
		if (nums == null || nums.length < 2) {
			return 0;
		}
		return mergeSort(nums,0,nums.length-1);
	}

	private int mergeSort(int[] nums,int l,int r) {
		if(l==r){
			return 0;
		}
		int mid = l+((r-l)>>1);
		return mergeSort(nums,l,mid)+mergeSort(nums,mid+1,r)+merge(nums,l,r,mid);
	}

	private int merge(int[] nums, int l, int r,int mid) {
		int temp[] = new int[r-l+1];
		int index = 0;
		int lIndex = l;
		int rIndex = mid+1;

		int count=0;
		// lIndex  rIndex 不回退  排序加速求解
		///  10 8 4 2    5 4 3 2
		while (lIndex<=mid&&rIndex<=r){
			if(nums[lIndex]>(long)nums[rIndex]*2){
				count+=r-rIndex+1;
				lIndex++;
			}else{
				rIndex++;
			}
		}
		lIndex = l;
		rIndex = mid+1;
		while (lIndex<=mid&&rIndex<=r){
			temp[index++] = nums[lIndex]>=nums[rIndex]?nums[lIndex++]:nums[rIndex++];
		}
		while (lIndex<=mid){
			temp[index++] =  nums[lIndex++];
		}

		while (rIndex<=r){
			temp[index++] =  nums[rIndex++];
		}
		lIndex = l;
		for (int val : temp) {
			nums[lIndex++] = val;
		}
		return count;
	}
}
